package main

var (
	dx = []int{1, 0, 0, -1}
	dy = []int{0, 1, -1, 0}
)

//广度优先搜索
func floodFill1(image [][]int, sr int, sc int, newColor int) [][]int {
	//存个最初颜色
	currColor := image[sr][sc]
	if currColor == newColor {
		return image
	}
	//存放顶点的队列
	queue := [][]int{}
	queue = append(queue, []int{sr, sc})
	image[sr][sc] = newColor
	n, m := len(image), len(image[0])
	for i := 0; i < len(queue); i++ {
		//将要染色的点
		cell := queue[i]
		//搜索临近的四个点
		for j := 0; j < 4; j++ {
			//计算坐标
			mx, my := cell[0]+dx[j], cell[1]+dy[j]
			//判断边界、是否与原色相同
			if mx >= 0 && my >= 0 && mx < n && my < m && currColor == image[mx][my] {
				image[mx][my] = newColor
				queue = append(queue, []int{mx, my})
			}
		}
	}
	return image
}

//深度优先搜索
func floodFill2(image [][]int, sr int, sc int, newColor int) [][]int {
	if image[sr][sc] == newColor {
		return image
	}
	dfs(image, sr, sc, newColor)
	return image
}

func dfs(image [][]int, sr int, sc int, newColor int) {
	currColor := image[sr][sc]
	image[sr][sc] = newColor
	for i := 0; i < 4; i++ {
		mx, my := sr+dx[i], sc+dy[i]
		if mx >= 0 && my >= 0 && mx < len(image) && my < len(image[0]) && currColor == image[mx][my] {
			dfs(image, mx, my, newColor)
		}
	}
}

func main() {

}
